<?php

// By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

// 3
// 7 4
// 2 4 6
// 8 5 9 3

// That is, 3 + 7 + 4 + 9 = 23.
// Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
// NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

$triangle = file("data/triangle.txt", FILE_USE_INCLUDE_PATH | FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES );

while (list($k,$v) = each($triangle)) {
	$triangle[$k] = explode(' ', $v);
}

for ($i = count($triangle)-2; $i >= 0; $i--) {
	for ($c=0; $c<count($triangle[$i]); $c++) {
		$triangle[$i][$c] += max($triangle[$i+1][$c], $triangle[$i+1][$c+1]);
	}
	unset($triangle[$i+1]);
}

echo "{$triangle[0][0]}\n";